一道小清新动规题。
题意:求长度为 的、最大数不超过 的数列,满足 ( 且 为正整数)。
思路:
容易想到设计状态 表示长度为 时最大数为 的方案总数。
转移方程也比较好想,根据数列要求,枚举所有可能的倍数,加上对应方案的 值即可。即:。由于因数不好统计,我们根据 来反推即可。
但是还没有结束,虽然我们可以通过此题,但是作为一个优(du)秀(liu)的 OIer,你不觉得 数组这么大很多余吗?我们对于每一个 ,只用到了 的 值,显然可以压缩空间啊!
考虑将 定义为最大数为 的方案总数,原本的 是没有必要存的。转移方程也没有特别大的变化。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2005, mod = 1e9+7;
ll n, k;
ll dp[N], tmp[N], ans;
int main() {
scanf("%lld%lld", &n, &k);
for(ll i=1;i<=n;i++) dp[i] = 1;
for(ll cnts=2;cnts<=k;cnts++) {
for(ll i=1;i<=n;i++) tmp[i] = 0;
for(ll i=1;i<=n;i++) {
for(ll j=1,_=i*j;_<=n;j++,_=i*j) tmp[_] = (tmp[_] + dp[i]) % mod;
}
for(ll i=1;i<=n;i++) dp[i] = tmp[i];
}
for(ll i=1;i<=n;i++) ans = (ans + dp[i]) % mod;
printf("%lld\n", ans);
return 0;
}